/**
 * \file BloomFilter.h
 * \brief No dependencies
 */

#ifndef __KEY_VALUE_FILE_BLOOM_FILTER_H_
#define __KEY_VALUE_FILE_BLOOM_FILTER_H_


namespace KeyValueFile
{
	/**
	 * \brief Template for Bloom filter hash functions
	 * \arg HashFunctionType - type of function to calculate hash of instance of Type
	 * \arg NumBits - number of bits to store set
	 * \arg NumHashFunctions - number of hash functions
	 */
	template< typename HashFunctionType, unsigned int NumBits, unsigned int NumFunctions >
	class BloomFilterHashFunctions
	{
	public:
		template< typename Type >
		unsigned int operator( )( unsigned int i, const Type& element ) const
		{
			return m_hashFunctions[ i ]( element ) % NumBits;
		}

	private:
		HashFunctionType m_hashFunctions[ NumFunctions ];
	};

	/**
	 * \brief Bloom filter
	 * \arg NumBits - number of bits to store set
	 * \arg NumHashFunctions - number of hash functions
	 */
	template< unsigned int NumBits, unsigned int NumHashFunctions >
	class BloomFilterStatic
	{
	public:
		/**
		 * \brief Amount of memory used by Bloom filter in bytes
		 */
		static
		const unsigned int NumUsedBytes = NumBits / 8 + 1;

	public:
		/**
		 * \brief Constructor clears set
		 */
		BloomFilterStatic( )
		{
			Clear( );
		}

		/**
		 * \brief Inserts element to set
		 * \arg Type - type of element
		 */
		template< typename Type, typename HashFunctionType >
		void Insert( const BloomFilterHashFunctions< HashFunctionType, NumBits, NumHashFunctions >& hashFunctions, const Type& element )
		{
			for( unsigned int i = 0; i < NumHashFunctions; ++i )
			{
				unsigned int bitIndex = hashFunctions( i, element );
				setBit( bitIndex );
			}
		}

		/**
		 * \brief Checks if element exists in set
		 * \arg Type - type of element
		 */
		template< typename Type, typename HashFunctionType >
		bool Find( const BloomFilterHashFunctions< HashFunctionType, NumBits, NumHashFunctions >& hashFunctions, const Type& element ) const
		{
			for( unsigned int i = 0; i < NumHashFunctions; ++i )
			{
				unsigned int bitIndex = hashFunctions( i, element );
				if( !testIsBitSet( bitIndex ) )
					return false;
			}

			return true;
		}

		/**
		 * \brief Clears set
		 */
		void Clear( )
		{
			for( unsigned int i = 0; i < NumUsedBytes; ++i )
				m_bits[ i ] = 0;
		}

	private:
		void setBit( unsigned int bitIndex )
		{
			m_bits[ bitIndex / 8 ] |= (1 << (bitIndex % 8));
		}

		bool testIsBitSet( unsigned int bitIndex ) const
		{
			return (m_bits[ bitIndex / 8 ] & (1 << (bitIndex % 8))) != 0;
		}

	private:
		unsigned char m_bits[ NumUsedBytes ];
	};
};

#endif